class Node:  
    """默认构造函数"""  
    def __init__(self, value = None, next_node=None):  
        self.value = value    # 节点的值  
        self.next = next_node # 指向下一个节点的引用 
    

class LinkedList:  
    """定义链表"""  
    def __init__(self):  
        self.head = None # 链表的头节点 

    # 头插  
    def push_front(self, value):  
        """在链表头部插入一个新节点"""  
        new_node = Node(value)  
        new_node.next = self.head # 新节点的 next 指向当前头节点  
        self.head = new_node      # 更新头节点为新节点  
  
    # 头删  
    def pop_front(self):  
        """删除链表头部的节点并返回其值"""  
        if self.head is None:  
            raise IndexError("Cannot pop from an empty linked list.")  
        res = self.head.value      # 获取要删除节点的值  
        self.head = self.head.next # 更新头节点为下一个节点  
        return res  
  
    # 尾插  
    def push_back(self, value):  
        """在链表尾部插入一个新节点"""  
        new_node = Node(value)  
        if self.head is None:    # 如果链表为空，新节点成为头节点  
            self.head = new_node  
        else:  
            curr = self.head     # 遍历到链表尾部
            while curr.next is not None:    
                curr = curr.next  
            curr.next = new_node # 在尾部插入新节点  
  
    # 尾删  
    def pop_back(self):  
        """删除链表尾部的节点并返回其值"""  
        if self.head is None:  
            raise IndexError("Cannot pop from an empty linked list.")  
        if self.head.next is None: # 如果链表只有一个节点  
            res = self.head.value  
            self.head = None       # 清空头节点  
            return res
          
        curr = self.head           # 遍历到倒数第二个节点
        while curr.next.next is not None:    
            curr = curr.next  
        res = curr.next.value      # 获取要删除节点的值  
        curr.next = None           # 删除尾节点  
        return res  
    
    # 查找
    def search(self, target):  
            """查找链表中第一个值为target的节点，并返回其节点对象"""  
            curr = self.head  
            while curr is not None:  
                if curr.value == target:  
                    return curr # 返回找到的节点对象  
                curr = curr.next  
            return None         # 如果未找到，返回None
  
    # 修改  
    def update(self, old_value, new_value):    
        """修改链表中第一个值为old_value的节点的值为new_value，并返回是否成功修改"""    
        node = self.search(old_value) # 查找节点    
        if node is not None:    
            node.value = new_value    
            return True               # 修改成功    
        return False                  # 未找到要修改的节点 
  
    # 打印  
    def print_list(self):  
        """打印链表中的所有节点值"""  
        curr = self.head  
        while curr is not None:  
            print(f"{curr.value}->", end="")  
            curr = curr.next  
        print("None")  
  

# 找到中间节点
def find_middle_node(head):  
    """  
    找到链表的中间结点  
    :param head: 链表的头结点  
    :return: 链表的中间结点  
    """  
    slow = head  
    fast = head  
      
    while fast is not None and fast.next is not None:  
        slow = slow.next  
        fast = fast.next.next  
      
    return slow  
  
# 示例测试  
if __name__ == "__main__":  
    ll = LinkedList()  
    for i in [1, 2, 3, 4, 5]:  
        ll.push_back(i)   
    middle_node = find_middle_node(ll.head)  
    print(f"中间结点的值为: {middle_node.value}")  # 输出: 3  
      
    ll = LinkedList()  
    for i in [1, 2, 3, 4, 5, 6]:  
        ll.push_back(i)  
    middle_node = find_middle_node(ll.head)  
    print(f"中间结点的值为: {middle_node.value}")  # 输出: 4